package main

import "fmt"

func merge(nums1 []int, m int, nums2 []int, n int) {
	nums := make([]int, 0)
	current := 0

	i, j := 0, 0
	// x, x, x []
	// x, x, x []
	for i <= m-1 && j <= n-1 {
		// 比较大小，大的再追加
		if nums1[i] <= nums2[j] {
			current = nums1[i]
			i++
		} else {
			current = nums2[j]
			j++
		}
		nums = append(nums, current)
	}

	// 剩余数据
	for i <= m-1 {
		nums = append(nums, nums1[i])
		i++
	}
	for j <= n-1 {
		nums = append(nums, nums2[j])
		j++
	}
	copy(nums1, nums)
}

func mergeV2(nums1 []int, m int, nums2 []int, n int) {
	index := m + n - 1
	current := 0

	i, j := m-1, n-1
	// x, x, x [] [] []
	// x, x, x
	for i >= 0 && j >= 0 {
		// 比较大小，大的再追加
		if nums1[i] >= nums2[j] {
			current = nums1[i]
			i--
		} else {
			current = nums2[j]
			j--
		}
		nums1[index] = current
		index--
	}

	// 剩余数据
	for j >= 0 {
		current = nums2[j]
		nums1[index] = current
		j--
		index--
	}
}

func main() {
	nums1 := []int{1, 2, 3, 0, 0, 0}
	nums2 := []int{2, 5, 6}
	m, n := 3, 3

	mergeV2(nums1, m, nums2, n)

	fmt.Println(nums1)
}
